package com.leetcode.partition7;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2021/12/14 20:02
 */
public class LC630课程表III {

    /**
     * 学习该课程后，满足「最晚完成时间」要求，即 sum + courses[i][0] <= courses[i][1]则进行学习；
     * 学习该课程后，不满足「最晚完成时间」要求，此时从过往学习的课程中找出「持续时间」最长的课程进行「回退」操作（这个持续时长最长的课程有可能是当前课程）。
     */
    public static int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (o1, o2) -> o1[1] == o2[1] ? Integer.compare(o1[0], o2[0]) : Integer.compare(o1[1], o2[1]));
        //大顶堆，堆顶存放开始时间最晚的课程
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));
        int sum = 0;
        for (int[] course : courses) {
            int duration = course[0], lastTime = course[1];
            sum += duration;
            queue.add(duration);
            //如果超时，从已经选的课程中移出最耗时的课程
            if (sum > lastTime) sum -= queue.poll();
        }
        return queue.size();
    }

    public static void main(String[] args) {
//        int[][] courses = {{100, 200}, {200, 1300}, {1000, 1250}, {2000, 3200}};
//        int[][] courses = {{3, 2}, {4, 3}};
        int[][] courses = {{5, 5}, {4, 6}, {2, 6}};
        System.out.println(scheduleCourse(courses));
    }
}
